package com.atguigu.tree.threadedbinarytree;

/**
 * @author RuiKnag
 * @create 2021-05-18-14:49
 */
public class ThreadedBinaryTree {
    public static void main(String[] args) {
        //测试中序线索二叉树的功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");
        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        //测试中序线索化
        BinaryTree threadedBinaryTree = new BinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();


        //测试: 以10号节点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1

        //使用线索化的方式，遍历该二叉树
        threadedBinaryTree.threadedList();

    }

}
class BinaryTree{
    private HeroNode root;
    //为了实现线索化，需要创建一个指向当前节点的前驱节点
    //在递归线索化的时候，保存前一个节点
    private HeroNode pre=null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //遍历中序线索二叉树的方法
    public void threadedList(){
        //定义一个指针指向当前遍历的根节点
        HeroNode node=root;
        while (node!=null){
            while(node.getLeftType()!=1){
                node=node.getLeft();
            }
            System.out.println(node);
            //查看当前节点的指针的右指针是否指向后继节点，一直输出
            while (node.getRightType()==1){
                //获取后继节点
                node=node.getRight();
                System.out.println(node);
            }
            node=node.getRight();
        }
    }


    //重写该方法
    public void threadedNodes(){
        threadedNodes(root);
    }
    //编写对二叉树中序线索化的方法
    public void threadedNodes(HeroNode node){
        if(node==null){
            return;
        }
        //1.先线索化左子树
        threadedNodes(node.getLeft());
        //2.线索化当前节点
        //让当前节点指向前一个节点
        if(node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //让前一个节点的右指针指向当前节点
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //变动pre的位置
        pre=node;
        //2.线索化右子树
        threadedNodes(node.getRight());
    }


    //删除节点
    public void deleteNode(int no){
        if(root!=null){
            if(root.getNo()==no){
                root=null;
            }else{
                root.deleteNode(no);
            }
        }else{
            System.out.println("二叉树为空树");
        }
    }
    //前序遍历
    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder(){
        if(this.root!=null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //后续遍历
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //前序查找
    public HeroNode preOrderSearch(int no){
        if(root!=null){
            return root.preOrderSearch(no);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }
    //中序查找
    public HeroNode infixOrderSearch(int no){
        if(root!=null){
            return root.infixOrderSearch(no);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }
    //后续查找
    public HeroNode postOrderSearch(int no){
        if(root!=null){
            return root.postOrderSearch(no);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }

}

//创建节点
class HeroNode {
    private int no;
    private String name;
    private  HeroNode left;
    private  HeroNode right;
    //0代表left指向左子树，1代表指向前序节点
    private int leftType;
    //0代表right指向右子树，1代表指向后序节点
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public  HeroNode getLeft() {
        return left;
    }

    public void setLeft( HeroNode left) {
        this.left = left;
    }

    public  HeroNode getRight() {
        return right;
    }

    public void setRight( HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //递归删除节点
    /*
     * 如果删除的是叶子节点，则删除叶子节点
     * 如果删除的是非叶子节点，则删除该子树
     * */
    public void deleteNode(int no){
        if(this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        if(this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        if(this.left!=null){
            this.left.deleteNode(no);
        }
        if(this.right!=null){
            this.right.deleteNode(no);
        }



    }
    /*
     * 分析二叉树的前中后序遍历
     * 1 传创建一颗二叉树
     * 2 前序遍历
     *   2.1 先输出当前节点（父节点）
     *   2.2 如果左节点不为空，则递归继续前序遍历
     *   2.2 如果右节点不为空，则递归继续谦虚遍历
     * 3 中序遍历
     *   3.1 如果当前节点的左节点不为空，则递归中序遍历
     *   3.2 输出当前父节点
     *   3.3 如果当前节点的右节点不为空，则递归中序遍历
     * 4 后序遍历
     *   4.1 如果当前节点的左节点不为空，则递归中序遍历
     *   4.2 如果当前节点的右节点不为空，则递归中序遍历前序遍历
     *   4.3 输出当前父节点
     */
    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }

    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    //后续遍历
    public void postOrder(){
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
    /*
     * 使用前中后序查找指定的节点：
     * 使用前序查找的思路：
     *   1先判断当前节点的no是否为要查找的
     *   2如果相等，则返回当前节点
     *   3如果不相等，则判断当前节点的左节点是否为空，如果不为空，则递归前序查找
     *   4如果左递归前序查找，找到该节点，则返回，否则继续判断，当前节点的右子节
     *   点是否为空，如果不为空，则继续右递归前序查找。
     *使用中序查找的思路
     *   1判断当前节点的左节点是否为空，如果不为空，则递归中序查找
     *   2如果找到该节点，则返回；如果没有找到该节点，就和当前节点进行比较，如果是，则返回当前节点，否则继续进行
     *   右递归的中序查找
     *   3如果右递归中序查找，找到就返回，否则返回null
     * 使用后续查找的思路
     *   1判断当前节点的左节点是否为空，如果不为空，则递归后序查找
     *   2如果找到，返回；如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到就返回
     *   3.和当前节点进行比较，如果是则返回，否则返回null。
     *
     *
     * */
    //前序查找

    public  HeroNode preOrderSearch(int no){
        System.out.println("前序查找");
//        1先判断当前节点的no是否为要查找的
//        2如果相等，则返回当前节点
        if (this.no==no){
            return this;
        }
        //3如果不相等，则判断当前节点的左节点是否为空，如果不为空，则递归前序查找
        //如果找到该节点，则返回
         HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.preOrderSearch(no);
        }
        if(resNode!=null){//说明在左子树找到了
            return resNode;
        }
        //继续判断，当前节点的右子节点点是否为空，如果不为空，则继续右递归前序查找。
        if(this.right!=null){
            resNode=this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //中序查找
    public  HeroNode infixOrderSearch(int no){
        /*
         * *使用中序查找的思路
         *   1判断当前节点的左节点是否为空，如果不为空，则递归中序查找
         *   2如果找到该节点，则返回；如果没有找到该节点，就和当前节点进行比较，如果是，则返回当前节点，否则继续进行
         *   右递归的中序查找
         *   3如果右递归中序查找，找到就返回，否则返回null
         * */

         HeroNode resNode=null;
        if(this.left!=null){
            resNode=this.left.infixOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("中序查找");
        if(this.no==no){
            return this;
        }
        if(this.right!=null){
            resNode=this.right.infixOrderSearch(no);
        }
        return resNode;

    }
    //后续查找
    public HeroNode postOrderSearch(int no){

       /* 使用后续查找的思路
          1判断当前节点的左节点是否为空，如果不为空，则递归后序查找
          2如果找到，返回；如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到就返回
          3和当前节点进行比较，如果是则返回，否则返回null。*/
        HeroNode resNode=null;
        if(this.left!=null){
            resNode=this.left.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if(this.right!=null){
            resNode=this.right.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("后序查找");
        if(this.no==no){
            return this;

        }
        return null;
    }
}
